96. 不同的二叉搜索树
96. 不同的二叉搜索树
分析
我们首先还是把 dp[i] 定义为 i 个节点有多少种满足二叉搜索树的种数，然后我们开始思考状态转移公式。
其实我们对于二叉树首先要明白一点，确定一个二叉树，其实第一步就是确定这个二叉树的根节点，而且对于一个由指定数字组成的二叉搜索树而言，确定了根节点，左子树有哪些节点跟右子树有哪些节点就确定了。
举个例子，n=3 的时候，有 1，2，3 三个节点，我们如何确定这三个节点能构成的二叉搜索树呢？
- 以 1 为根结点，左侧 0 个节点，右侧 2 个节点，两个节点可以构造成多少种二叉搜索树呢？
dp[2],也就是说，当我们选择 1 来当根节点的时候，只有dp[2]种方式， - 以 2 为根节点的时候，左侧有 1 个节点，右侧也只有 1 个节点，总共有
dp[1]*dp[1]种方式， - 以 3 为根节点的时候，左侧有 2 个节点，右侧有 0 个，总共有
dp[2]种方式
所以 dp[3] = dp[2] + dp[1]*dp[1] + dp[2]。
所以状态转移公式是 dp[i] = dp[i-1] + dp[i-2]*dp[1] + dp[i-3]*dp[2] + ... + dp[1]*dp[i-2] + ... + dp[i-1]；
总结一下：
子问题的嵌套：确定了根节点之后，左侧节点的个数就确定了，那么左侧子树有多少种摆法就确定了（子问题嵌套），同时右侧子树有多少种摆法就也确定了，相乘就是以当前节点为根节点的时候有多少种摆法。遍历所有节点，将以每一个节点为根节点的摆法加起来，就是最终答案
我们用动态规划解题，最重要的，就是找到问题是如何嵌套的，找到了问题如何嵌套，就找到了状态转移方程。
初始值就是 dp[1]=1。
n 从小到大进行遍历，从 2 开始。
解题
public int numTrees(int n) {
if(n==1){
return n;
}
int[] dp = new int[n+1];
dp[1]=1;
for(int i=2;i<=n;i++){
int count=0;
for(int j=1;j<=i;j++){
int leftNodeCount = j-1;
int rightNodeCount = i-j;
// 也可以把dp[0]初始化成1，但是是没有意义的，不要这样做。
int leftCount = leftNodeCount==0?1:dp[leftNodeCount];
int rightCount = rightNodeCount==0?1:dp[rightNodeCount];
count+=leftCount*rightCount;
}
dp[i]=count;
}
return dp[n];
}